import java.util.Random;

public class 数组中的第K个最大元素 {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums,0,nums.length - 1, k);
    }

    private int quickSort(int[] nums, int left, int right, int k) {
        if (left >right) {
            return -1;
        }
        if (left == right) {
            return nums[left];
        }
        // 边界值界定 [left,l] [l + 1,r - 1] [r,right]
        int l = left - 1;
        int r = right + 1;
        int key = nums[new Random().nextInt(right - left + 1) + left];
        int i  = left;
        while (i < r) {
            if (nums[i] < key) {
                swap(nums,i++,++l);
            } else if (nums[i] > key){
                swap(nums,i,--r);
            } else {
                i++;
            }
        }
        int rightLen = right - r + 1;
        int middleLen = r - l - 1;
        if (rightLen >= k) {
            return quickSort(nums,r,right,k);
        } else if (rightLen + middleLen >= k) {
            return key;
        } else {
            return quickSort(nums,left,l,k - rightLen - middleLen);
        }
    }
    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}
